package site.wanjiahao.union;

/**
 * Quick Find
 * find O(1)
 * Union O(n)
 */
public class UnionFind_QF extends UnionFind{

    public UnionFind_QF(int capacity) {
        super(capacity);
    }

    /***
     * Quick Find查找为O(1)的级别，直接查看当前元素的父元素，不需要在向上寻找
     * @Author: haogege
     * @Date: 2021/9/8
     */
    @Override
    public int find(int v) {
        checkRange(v);
        return parents[v];
    }

    // 将v1集合中的所有元素隶属于v2
    @Override
    public void union(int v1, int v2) {
        // 查找v1中的所有元素
        // v1元素的父节点
        int p1 = find(v1);
        // v2元素的父节点
        int p2 = find(v2);
        if (p1 == p2) return;
        for (int i = 0; i < parents.length; i++) {
            // 将所有是p1父节点的，隶属于p2, 左边归于右边
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }
}
